package com.lw.leetcode.sort;

import java.util.Arrays;

/**
 * 剑指 Offer 40. 最小的k个数
 *
 * @Author liw
 * @Date 2021/5/18 17:43
 * @Version 1.0
 */
public class GetLeastNumbers {

    public static void main(String[] args) {
        GetLeastNumbers test = new GetLeastNumbers();
        int[] arr= {0,0,1,2,4,2,2,3,1,4};
        int[] leastNumbers = test.getLeastNumbers(arr, 8);
        System.out.println(Arrays.toString(leastNumbers));
    }

    public int[] getLeastNumbers(int[] arr, int k) {

        if (arr == null || arr.length == 0) {
            return  new int[0];
        }
        if (k == 0) {
            return new int[0];
        }
        int length = arr.length;
        int limit = length - 1;
        for(int i = (length >> 1) - 1; i >= 0; i--){
            sort(arr, i, limit);
        }

        int[] values = new int[k];
        values[0] = arr[0];
        arr[0] = arr[limit];
        for (int i = 1; i < k; i++) {
            sort(arr, 0, limit - i);
            values[i] = arr[0];
            arr[0] = arr[limit - i];
        }
        return values;
    }

    private void sort (int[] arr, int st, int end) {

        int l = (st << 1) + 1;
        if (l > end) {
            return;
        }
        l = l + 1 <= end ? (arr[l] < arr[l + 1] ? l : l + 1) : l;
        if (arr[l] < arr[st] ) {
            int item = arr[l];
            arr[l] = arr[st];
            arr[st] = item;
            sort(arr, l, end);
        }
    }

}
